package com.leet.code.lcof;

import com.algorithm.BinaryTree;
import com.algorithm.model.TreeNode;

import java.util.ArrayList;
import java.util.List;

public class Code07 {

    public static void main(String[] args) {
        int[] preorder = {3, 9, 11, 12, 20, 15, 7};
//        int[] preorder = {3, 9, 20, 15, 7};
        int[] inorder = {11, 12, 9, 3, 15, 20, 7};
//        int[] inorder = {9, 3, 15, 20, 7};
//        BinaryTree.preorder(buildTree(preorder, inorder));
        BinaryTree.inorder(buildTree(preorder, inorder));
        BinaryTree.print();

    }

    public static TreeNode buildTree(int[] preorder, int[] inorder) {
        List<Integer> preList = new ArrayList<>();
        List<Integer> inList = new ArrayList<>();
        for (int i = 0; i < preorder.length; i++) {
            preList.add(preorder[i]);
            inList.add(inorder[i]);
        }
        return buildTree(preList, inList);
    }

    public static TreeNode buildTree(List<Integer> preorder, List<Integer> inorder) {

        if (inorder.isEmpty()) {
            return null;
        }
        int rootVal = preorder.remove(0);
        TreeNode rootNode = new TreeNode(rootVal);

        int i = inorder.indexOf(rootVal);

        rootNode.left = buildTree(preorder, inorder.subList(0, i));
        rootNode.right = buildTree(preorder, inorder.subList(i + 1, inorder.size()));
        return rootNode;
    }


}
